package previous.Test_0119;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class exercise {
    //移动零:双指针
    //给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
    //cur：从左到右遍历数组，遍历数组元素；
    //dest：已处理的区间，非零元素的最后一个位置；
    //[0,dest]表示非零区间；[dest+1,cur-1]零区间，[cur,n-1]待处理区间
    public void swap(int i,int j,int nums[]){
        int t=nums[i];
        nums[i]=nums[j];
        nums[j]=t;
    }
    public void moveZeroes(int[] nums) {
        int cur=0;
        int dest=-1;
        for (int i = 0; i < nums.length; i++) {
            if(nums[cur]==0){
                cur++;
            }else{
                swap(cur,dest+1,nums);
                dest++;
                cur++;
            }
        }
    }
    //复写零：双指针
//题目：给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
/*先找到最后一个元素
快慢指针法：
fast和slow；
如果slow遇到0，fast向后移动两位，否则移动一位*/
    public static void duplicateZeros1(int[] arr) {
        int cur =0;
        int dest=-1;
        int len=arr.length;
        //找到最后一位元素
        while(cur<len){
            if(arr[cur]!=0){
                dest++;
            }else{
                dest+=2;
            }
            if(dest>=len-1) break;
            cur++;
        }
        if(dest>=len){
            arr[len-1]=0;
            cur--;
            dest-=2;
        }
        //复写
        while(cur>=0){
            if(arr[cur]!=0){
                arr[dest]=arr[cur];
                dest--;
            }else{
                arr[dest--]=0;
                arr[dest--]=0;
            }
            cur--;
        }
    }
    public void duplicateZeros2(int[] arr) {
        int cur = 0;
        int dest = -1;
        int len = arr.length;
        //找到最后一位元素
        while (cur < len) {
            if (arr[cur] != 0) {
                dest++;
            } else {
                dest += 2;
            }
            if(dest>=len-1) break;
            cur++;
        }
        if (dest >= len) {
            arr[len - 1] = 0;
            cur--;
            dest -= 2;
        }
        //复写
        while (cur >= 0) {
            if (arr[cur] != 0) {
                arr[dest] = arr[cur];
                dest--;
            } else {
                arr[dest--] = 0;
                arr[dest--] = 0;
            }
            cur--;
        }
    }
    //快乐数:循环 快慢双指针，总会相遇
//编写一个算法来判断一个数 n 是不是快乐数
    public int bitSum(int num){
        int sum=0;
        while(num!=0){
            int a=num%10;
            sum+=a*a;
            num=num/10;
        }
        return sum;
    }
    public boolean isHappy(int n) {
        int slow=n;
        int fast=bitSum(n);
        while(slow!=fast){
            slow=bitSum(slow);
            fast=bitSum(bitSum(fast));
        }
        return slow==1;
    }
    //盛最多水的容器：单调性，双指针
/*给定一个长度为 n 的整数数组 height 。
有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。*/
    public int maxArea(int[] height) {
        int left=0;
        int right=height.length-1;
        int V=0;
        int max=0;
        while(left!=right){
            if(height[left]<height[right]){
                V=(right-left)*height[left];
                left++;
            }else{
                V=(right-left)*height[right];
                right--;
            }
            if(max<V){
                max=V;
            }
        }
        return max;
    }
    //改进
    public int maxArea2(int[] height) {
        int left=0;
        int right=height.length-1;
        int V=0;
        int max=0;
        while(left!=right){
            V=Math.min(height[left],height[right])*(right-left);
            max=Math.max(V,max);
            if(height[left]<height[right]){
                left++;
            }else{
                right--;
            }
        }
        return max;
    }
}
